home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Diamond Collection / The Diamond Collection (Software Vault)(Digital Impact).ISO / cdr44 / frasrc19.zip / DECODER.C < prev    next >
C/C++ Source or Header  |  1995-03-04  |  14KB  |  458 lines
  1. /* DECODE.C - An LZW decoder for GIF
  2.  * Copyright (C) 1987, by Steven A. Bennett
  3.  *
  4.  * Permission is given by the author to freely redistribute and include
  5.  * this code in any program as long as this credit is given where due.
  6.  *
  7.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  8.  * the code which this is heavily inspired by...
  9.  *
  10.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  11.  * Compuserve, Incorporated, an H&R Block Company.
  12.  *
  13.  * Release Notes: This file contains a decoder routine for GIF images
  14.  * which is similar, structurally, to the original routine by Steve Wilhite.
  15.  * It is, however, somewhat noticably faster in most cases.
  16.  *
  17.  == This routine was modified for use in FRACTINT in two ways.
  18.  ==
  19.  == 1) The original #includes were folded into the routine strictly to hold
  20.  ==    down the number of files we were dealing with.
  21.  ==
  22.  == 2) The 'stack', 'suffix', 'prefix', and 'decoderline' arrays were changed from
  23.  ==    static and 'malloc()'ed to external only so that the assembler
  24.  ==    program could use the same array space for several independent
  25.  ==    chunks of code.    Also, 'stack' was renamed to 'dstack' for TASM
  26.  ==    compatibility.
  27.  ==
  28.  == 3) The 'out_line()' external function has been changed to reference
  29.  ==    '*outln()' for flexibility (in particular, 3D transformations)
  30.  ==
  31.  == 4) A call to 'keypressed()' has been added after the 'outln()' calls
  32.  ==    to check for the presenc of a key-press as a bail-out signal
  33.  ==
  34.  == (Bert Tyler and Timothy Wegner)
  35.  */
  36.  
  37. /* Rev 01/02/91 - Revised by Mike Gelvin
  38.  *              altered logic to allow newcode to input a line at a time
  39.  *              altered logic to allow decoder to place characters
  40.  *              directly into the output buffer if they fit
  41.  * Rev 03/02/95 - Revised by Tim Wegner
  42.  *              made sizeofstring local pointing to extraseg
  43. */
  44.  
  45. /***** C Library Includes ***********************************************/
  46. #include <stdio.h>
  47.  
  48. /***** Application Includes *********************************************/
  49. #include "prototyp.h"
  50.  
  51. /***** Application Function Prototypes **********************************/
  52. static short get_next_code(void);
  53.  
  54. /* extern short out_line(pixels, linelen)
  55.  *     UBYTE pixels[];
  56.  *     short linelen;
  57.  *
  58.  *   - This function takes a full line of pixels (one byte per pixel) and
  59.  * displays them (or does whatever your program wants with them...).  It
  60.  * should return zero, or negative if an error or some other event occurs
  61.  * which would require aborting the decode process...  Note that the length
  62.  * passed will almost always be equal to the line length passed to the
  63.  * decoder function, with the sole exception occurring when an ending code
  64.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  65.  * equal to the number of pixels passed...
  66.  */
  67. int (*outln)(BYTE *,int) = out_line;
  68.  
  69. /***** Local Static Variables *******************************************/
  70. /* Various error codes used by decoder
  71.  * and my own routines...   It's okay
  72.  * for you to define whatever you want,
  73.  * as long as it's negative...  It will be
  74.  * returned intact up the various subroutine
  75.  * levels...
  76.  */
  77. #define OUT_OF_MEMORY -10
  78. #define BAD_CODE_SIZE -20
  79. #define READ_ERROR -1
  80. #define WRITE_ERROR -2
  81. #define OPEN_ERROR -3
  82. #define CREATE_ERROR -4
  83.  
  84. /* #define MAX_CODES   4095 */ /* moved to Fractint.h */
  85.  
  86. #define NOPE 0
  87. #define YUP -1
  88.  
  89. static short curr_size;            /* The current code size */
  90.  
  91.  
  92. /* The following static variables are used
  93.  * for seperating out codes
  94.  */
  95. static short navail_bytes;        /* # bytes left in block */
  96. static short nbits_left;        /* # bits left in current byte */
  97. static BYTE byte_buff[257];    /* Current block, reuse shared mem */
  98. static BYTE *pbytes;        /* Pointer to next byte in block */
  99.  
  100. static short code_mask[13] = {
  101.      0,
  102.      0x0001, 0x0003,
  103.      0x0007, 0x000F,
  104.      0x001F, 0x003F,
  105.      0x007F, 0x00FF,
  106.      0x01FF, 0x03FF,
  107.      0x07FF, 0x0FFF
  108.      };
  109.  
  110. /***** External Variables ***********************************************/
  111. /* extern short bad_code_count;
  112.  *
  113.  * This value is the only other global required by the using program, and
  114.  * is incremented each time an out of range code is read by the decoder.
  115.  * When this value is non-zero after a decode, your GIF file is probably
  116.  * corrupt in some way...
  117.  *
  118.  * whups, here are more globals, added by PB: 
  119.  * extern short skipxdots;  0 to get every dot, 1 for every 2nd, 2 every 3rd, ...
  120.  * extern short skipydots; 
  121.  *
  122.  * All external declarations now in PROTOTYPE.H
  123.  */
  124.  
  125.  
  126. /*
  127. I removed the LOCAL identifiers in the arrays below and replaced them
  128. with 'extern's so as to declare (and re-use) the space elsewhere.
  129. The arrays are actually declared in the assembler source.
  130.                         Bert Tyler
  131. */
  132.  
  133. #if 0
  134. /* declarations moved to PROTOTYPE.H - these left for documentation */
  135.  BYTE dstack[MAX_CODES + 1];            /* Stack for storing pixels */
  136.  BYTE suffix[MAX_CODES + 1];            /* Suffix table */
  137.  unsigned short prefix[MAX_CODES + 1];        /* Prefix linked list */
  138.  BYTE decoderline[2];                /* decoded line goes here */
  139. #endif
  140.  
  141. /* The reason we have these separated like this instead of using
  142.  * a structure like the original Wilhite code did, is because this
  143.  * stuff generally produces significantly faster code when compiled...
  144.  * This code is full of similar speedups...  (For a good book on writing
  145.  * C for speed or for space optimization, see Efficient C by Tom Plum,
  146.  * published by Plum-Hall Associates...)
  147.  */
  148.  
  149.  
  150. /***** Program **********************************************************/
  151. /* short decoder(linewidth)
  152.  *    short linewidth;            * Pixels per line of image *
  153.  *
  154.  * - This function decodes an LZW image, according to the method used
  155.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  156.  * will generate a call to out_line(), which is a user specific function
  157.  * to display a line of pixels.  The function gets its codes from
  158.  * get_next_code() which is responsible for reading blocks of data and
  159.  * seperating them into the proper size codes.    Finally, get_byte() is
  160.  * the global routine to read the next byte from the GIF file.
  161.  *
  162.  * It is generally a good idea to have linewidth correspond to the actual
  163.  * width of a line (as specified in the Image header) to make your own
  164.  * code a bit simpler, but it isn't absolutely necessary.
  165.  *
  166.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  167.  *
  168.  */
  169. short decoder( short linewidth)
  170. {
  171. #ifndef XFRACT
  172.     static short far *sizeofstring;
  173. #else
  174.     extern int prefix[];
  175.     short sizeofstring[MAX_CODES+1];    /* size of string list */
  176. #endif
  177.     BYTE *sp;
  178.     short code;
  179.     short old_code;
  180.     short ret;
  181.     short c;
  182.     short size;
  183.     short i;
  184.     short j;
  185.     short fastloop;
  186.     short bufcnt;                    /* how many empty spaces left in buffer */
  187.     short xskip;
  188.     short slot;                        /* Last read code */
  189.     short newcodes;                    /* First available code */
  190.     BYTE *bufptr;
  191.     short yskip;
  192.     short top_slot;                    /* Highest code for current size */
  193.     short clear;                    /* Value for a clear code */
  194.     short ending;                    /* Value for a ending code */
  195.     BYTE out_value;
  196.  
  197. #ifndef XFRACT
  198.     sizeofstring = (short far *)MK_FP(extraseg, 0);
  199. #endif
  200.     /* Initialize for decoding a new image...
  201.     */
  202.  
  203.     if ((size = (short)get_byte()) < 0)
  204.         return(size);
  205.     if (size < 2 || 9 < size)
  206.         return(BAD_CODE_SIZE);
  207.  
  208.     curr_size = (short)(size + 1);
  209.     top_slot = (short)(1 << curr_size);
  210.     clear = (short)(1 << size);
  211.     ending = (short)(clear + 1);
  212.     slot = newcodes = (short)(ending + 1);
  213.     navail_bytes = nbits_left = sizeofstring[slot] = xskip = yskip
  214.         = old_code = 0;
  215.     out_value = 0;
  216.     for (i = 0; i < slot; i++)
  217.     {    sizeofstring[i] = 0;
  218.     }
  219.     
  220.     /* Initialize in case they forgot to put in a clear code.
  221.      * (This shouldn't happen, but we'll try and decode it anyway...)
  222.     */
  223.  
  224.     /* Set up the stack pointer and decode buffer pointer
  225.     */
  226.     sp = dstack;
  227.     bufptr = decoderline;
  228.     bufcnt = linewidth;
  229.  
  230.     /* This is the main loop.  For each code we get we pass through the
  231.      * linked list of prefix codes, pushing the corresponding "character" for
  232.      * each code onto the stack.  When the list reaches a single "character"
  233.      * we push that on the stack too, and then start unstacking each
  234.      * character for output in the correct order.  Special handling is
  235.      * included for the clear code, and the whole thing ends when we get
  236.      * an ending code.
  237.     */
  238.     while ((c = get_next_code()) != ending)
  239.     {
  240.  
  241.         /* If we had a file error, return without completing the decode
  242.         */
  243.         if (c < 0)
  244.             return(0);
  245.  
  246.         /* If the code is a clear code, reinitialize all necessary items.
  247.         */
  248.         if (c == clear)
  249.         {
  250.             curr_size = (short)(size + 1);
  251.             slot = newcodes;
  252.             sizeofstring[slot] = 0;
  253.             top_slot = (short)(1 << curr_size);
  254.  
  255.             /* Continue reading codes until we get a non-clear code
  256.              * (Another unlikely, but possible case...)
  257.             */
  258.             while ((c = get_next_code()) == clear)
  259.             ;
  260.  
  261.             /* If we get an ending code immediately after a clear code
  262.              * (Yet another unlikely case), then break out of the loop.
  263.             */
  264.             if (c == ending)
  265.                 break;
  266.  
  267.             /* Finally, if the code is beyond the range of already set codes,
  268.              * (This one had better NOT happen...    I have no idea what will
  269.              * result from this, but I doubt it will look good...) then set it
  270.              * to color zero.
  271.             */
  272.             if (c >= slot)
  273.                 c = 0;
  274.  
  275.             out_value = (BYTE)(old_code = c);
  276.  
  277.             /* And let us not forget to put the char into the buffer... */
  278.             *sp++ = (BYTE)c;
  279.         }
  280.         else
  281.         {
  282.  
  283.             /* In this case, it's not a clear code or an ending code, so
  284.              * it must be a code code...  So we can now decode the code into
  285.              * a stack of character codes. (Clear as mud, right?)
  286.             */
  287.             code = c;
  288.  
  289.             /* Here we go again with one of those off chances...  If, on the
  290.              * off chance, the code we got is beyond the range of those already
  291.              * set up (Another thing which had better NOT happen...) we trick
  292.              * the decoder into thinking it actually got the next slot avail.
  293.             */
  294.  
  295.             if (code >= slot)
  296.             {
  297.                 if (code > slot)
  298.                 {
  299.                     ++bad_code_count;
  300.                     c = slot;
  301.                 }
  302.                 code = old_code;
  303.                 *sp++ = out_value;
  304.             }
  305.  
  306.             /* Here we scan back along the linked list of prefixes.  If they can
  307.              * fit into the output buffer then transfer them direct.  ELSE push
  308.              * them into the stack until we are down to enough characters that
  309.              * they do fit.  Output the line then fall through to unstack the ones
  310.              * that would not fit.
  311.             */
  312.             fastloop = NOPE;
  313.             while (code >= newcodes)
  314.             {    j = i = sizeofstring[code];
  315.                 if (i > 0 && bufcnt - i > 0 && skipxdots == 0)
  316.                 {
  317.                     fastloop = YUP;
  318.  
  319.                     do
  320.                     {    *(bufptr + j) = suffix[code];
  321.                         code = prefix[code];
  322.                     } while(--j > 0);
  323.                     *bufptr = (BYTE)code;
  324.                     bufptr += ++i;
  325.                     bufcnt -= i;
  326.                     if (bufcnt == 0) /* finished an input row? */
  327.                     {    if (--yskip < 0)
  328.                         {
  329.                             if ((ret = (short)((*outln)(decoderline, bufptr - decoderline))) < 0)
  330.                                 return(ret);
  331.                             yskip = skipydots;
  332.                         }
  333.                         if (keypressed())
  334.                             return(-1);
  335.                         bufptr = decoderline;
  336.                         bufcnt = linewidth;
  337.                         xskip = 0;
  338.                     }
  339.                 }
  340.                 else
  341.                 {
  342.                     *sp++ = suffix[code];
  343.                     code = prefix[code];
  344.                 }
  345.             }
  346.  
  347.             /* Push the last character on the stack, and set up the new
  348.              * prefix and suffix, and if the required slot number is greater
  349.              * than that allowed by the current bit size, increase the bit
  350.              * size.  (NOTE - If we are all full, we *don't* save the new
  351.              * suffix and prefix...  I'm not certain if this is correct...
  352.              * it might be more proper to overwrite the last code...
  353.             */
  354.             if (fastloop == NOPE)
  355.                 *sp++ = (BYTE)code;
  356.  
  357.             if (slot < top_slot)
  358.             {
  359.                 sizeofstring[slot] = (short)(sizeofstring[old_code]+1);
  360.                 suffix[slot] = out_value = (BYTE)code;
  361.                 prefix[slot++] = old_code;
  362.                 old_code = c;
  363.             }
  364.             if (slot >= top_slot)
  365.                 if (curr_size < 12)
  366.                 {
  367.                     top_slot <<= 1;
  368.                     ++curr_size;
  369.                 }
  370.         }
  371.         while (sp > dstack)
  372.         {
  373.             --sp;
  374.             if (--xskip < 0)
  375.             {
  376.                 xskip = skipxdots;
  377.                 *bufptr++ = *sp;
  378.             }
  379.             if (--bufcnt == 0) /* finished an input row? */
  380.             {    if (--yskip < 0)
  381.                 {
  382.                     if ((ret = (short)((*outln)(decoderline, bufptr - decoderline))) < 0)
  383.                         return(ret);
  384.                     yskip = skipydots;
  385.                 }
  386.                 if (keypressed())
  387.                     return(-1);
  388.                 bufptr = decoderline;
  389.                 bufcnt = linewidth;
  390.                 xskip = 0;
  391.             }
  392.         }
  393.  
  394.     }
  395.     /* PB note that if last line is incomplete, we're not going to try
  396.      * to emit it;  original code did, but did so via out_line and therefore
  397.      * couldn't have worked well in all cases...
  398.     */
  399.     return(0);
  400. }
  401.  
  402.  
  403.  
  404.  
  405. /***** Program **********************************************************/
  406. /* get_next_code()
  407.  * - gets the next code from the GIF file.  Returns the code, or else
  408.  * a negative number in case of file errors...
  409.  */
  410. static short get_next_code()
  411. {
  412.     static BYTE b1;                /* Current byte */
  413.     static unsigned short ret_code;
  414.  
  415.     if (nbits_left == 0)
  416.     {
  417.         if (navail_bytes <= 0)
  418.         {
  419.  
  420.             /* Out of bytes in current block, so read next block
  421.             */
  422.             pbytes = byte_buff;
  423.             if ((navail_bytes = (short)get_byte()) < 0)
  424.                 return(navail_bytes);
  425.             else
  426.                 if (navail_bytes)
  427.                     get_bytes(byte_buff,navail_bytes);
  428.         }
  429.         b1 = *pbytes++;
  430.         nbits_left = 8;
  431.         --navail_bytes;
  432.     }
  433.  
  434.     ret_code = (short)(b1 >> (8 - nbits_left));
  435.     while (curr_size > nbits_left)
  436.     {
  437.         if (navail_bytes <= 0)
  438.         {
  439.  
  440.             /* Out of bytes in current block, so read next block
  441.             */
  442.             pbytes = byte_buff;
  443.             if ((navail_bytes = (short)get_byte()) < 0)
  444.                 return(navail_bytes);
  445.             else
  446.                 if (navail_bytes)
  447.                     get_bytes(byte_buff,navail_bytes);
  448.         }
  449.         b1 = *pbytes++;
  450.         ret_code |= b1 << nbits_left;
  451.         nbits_left += 8;
  452.         --navail_bytes;
  453.     }
  454.     nbits_left -= curr_size;
  455.     return((short)(ret_code & code_mask[curr_size]));
  456. }
  457.  
  458.